//Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle
// containing only 1's and return its area.
//
// 
// Example 1: 
//
// 
//Input: matrix = [ ["1","0","1","0","0"],
//                  ["1","0","1","1","1"],
//                  ["1","1","1","1","1"],
//                  ["1","0","0","1","0"]]
//Output: 6[ ["1","0","1","0","0"],
////                  ["1","0","1","1","1"],
////                  ["1","1","1","1","1"],
////                  ["1","0","0","1","0"]]
//Explanation: The maximal rectangle is shown in the above picture.
// 
//
// Example 2: 
//
// 
//Input: matrix = []
//Output: 0
// 
//
// Example 3: 
//
// 
//Input: matrix = [["0"]]
//Output: 0
// 
//
// Example 4: 
//
// 
//Input: matrix = [["1"]]
//Output: 1
// 
//
// Example 5: 
//
// 
//Input: matrix = [["0","0"]]
//Output: 0
// 
//
// 
// Constraints: 
//
// 
// rows == matrix.length 
// cols == matrix[i].length 
// 0 <= row, cols <= 200 
// matrix[i][j] is '0' or '1'. 
// 
// Related Topics 栈 数组 哈希表 动态规划 
// 👍 896 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

import java.util.Stack;

//Java：Maximal Rectangle
class P85MaximalRectangle {
    public static void main(String[] args) {
        Solution solution = new P85MaximalRectangle().new Solution();
        // TO TEST
        Assert.assertEquals(solution.maximalRectangle(new char[][]
                {{'1', '0', '1', '0', '0'},
                        {'1', '0', '1', '1', '1'},
                        {'1', '1', '1', '1', '1'},
                        {'1', '0', '0', '1', '0'}}), 6);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maximalRectangle(char[][] matrix) {
            if (matrix == null || matrix.length == 0) {
                return 0;
            }
            int m = matrix.length, n = matrix[0].length;
            int max = 0;
            int[] heights = new int[n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '1') {
                        heights[j] += 1;
                    } else {
                        heights[j] = 0;
                    }
                }
                max = Math.max(max, largestRectangleArea(heights));
            }
            return max;
        }


        int largestRectangleArea(int heights[]) {
            Stack<Integer> stack = new Stack<>();
            int[] arr = new int[heights.length + 2];
            System.arraycopy(heights, 0, arr, 1, heights.length);
            int area = 0;
            for (int i = 0; i < arr.length; i++) {
                while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                    int h = arr[stack.pop()];
                    area = Math.max(area, (i - stack.peek() - 1) * h);
                }
                stack.push(i);
            }
            return area;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}